package sortingAdvance.mergeSortBU;

import java.util.Arrays;

/**
 * 自底向上的归并排序，优化
 * mxf
 * 2018年5月24日11:01:43
 */
public class MergeSortBUAdvance {

    public static void sort(Comparable[] arr) {
        int length = arr.length;

        // 没有优化的自底向上的归并
//        for(int sz = 1; sz < length; sz *= 2) {
//            for(int i = 0; i < length - sz; i += 2 * sz) {
//                merge(arr, i, i + sz - 1, Math.min(i + 2 * sz - 1, length - 1));
//            }
//        }
        // 对于小数组, 使用插入排序优化
        for(int i = 0; i < length; i += 16) {
            InsertionSort.sort(arr, i, Math.min(i + 15, length - 1));
        }

        for(int sz = 16; sz < length; sz *= 2) {
            for(int i = 0; i < length - sz; i += 2 * sz) {
                if( arr[i+sz-1].compareTo(arr[i+sz]) > 0 )
                    merge(arr, i, i + sz - 1, Math.min(i + 2 * sz - 1, length - 1));
            }
        }
    }

    /**
     * 归并
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(Comparable[] arr, int l, int mid, int r) {
        int m = l;
        int n = mid + 1;
        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);// 开辟一个临时空间, 不包含to位置的元素

        for(int i = l; i <= r; i++) {
            if(m > mid) {
                arr[i] = aux[n - l];
                n++;
            } else if(n > r) {
                arr[i] = aux[m - l];
                m++;
            } else if(aux[m - l].compareTo(aux[n - l]) > 0) {
                arr[i] = aux[n - l];
                n++;
            } else {
                arr[i] = aux[m - l];
                m++;
            }
        }
    }


    public static void main(String[] args) {
        Integer[] arr = SortTestHelper.generateRandomArray(1000000, 0, 1000000);
        sort(arr);
        System.out.println(SortTestHelper.isSorted(arr));
    }

}
